/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：SplayTree.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-03-31
Function List ：
Description   ：Splay Tree(Bottom-up)
******************************************************/

#include "SplayTree.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"
#include "LinkedStack.h"
#include "LinkedQueue.h"

struct SplayNode {
    ElementType Element;
    SplayTree   Parent;
    SplayTree   Left;
    SplayTree   Right;
};

// Static Function Lists
static Position FindValue(ElementType X, SplayTree T);
static SplayTree Splay(Position X, SplayTree T);
static Position SingleRotateWithLeft(Position K2);
static Position SingleRotateWithRight(Position K1);
static Position DoubleRotateWithLeft(Position K3);
static Position DoubleRotateWithRight(Position K1);

// Static Variable Lists
static Position NullNode = NULL;  /* Needs initialization */

SplayTree Initialize(void) {
    if (NullNode == NULL) {
        NullNode = (SplayTree)malloc(sizeof(struct SplayNode));
        if (NullNode == NULL) {
            FatalError("Out of space!!!");
        }

        NullNode->Parent = NullNode;
        NullNode->Left = NullNode;
        NullNode->Right = NullNode;
    }

    return NullNode;
}

SplayTree MakeEmpty(SplayTree T) {
    if (T != NullNode) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }

    return NullNode;
}

int IsEmpty(SplayTree T) {
    return T == NULL || T == NullNode;
}

Position Find(ElementType X, SplayTree T) {
    Position S;

    S = FindValue(X, T);
    if (S == NullNode) {
        return T;
    } else {
        return Splay(S, T);
    }
}

// Non-recursive implement
Position FindMin(SplayTree T) {
    Position S;

    S = T;
    if (S != NullNode) {
        while (S->Left != NullNode) {
            S = S->Left;
        }
    }

    return Splay(S, T);
}

// Non-recursive implement
Position FindMax(SplayTree T) {
    Position S;

    S = T;
    if (S != NullNode) {
        while (S->Right != NullNode) {
            S = S->Right;
        }
    }

    return Splay(S, T);
}

static Position FindValue(ElementType X, SplayTree T) {
    if (T == NullNode) {
        return NullNode;
    }

    if (X < T->Element) {
        return Find(X, T->Left);
    } else if (X > T->Element) {
        return Find(X, T->Right);
    } else {
        return T;
    }
}

static SplayTree Splay(Position S, SplayTree T) {
    Position P;
    Position G;

    while (S->Parent != NullNode) {
        P = S->Parent;
        G = P->Parent;
        /* If S is the left child of P */
        if (S == P->Left) {
            if (G == NullNode) {
                SingleRotateWithLeft(P);
            } else if (P == G->Left) {
                SingleRotateWithLeft(G);
                SingleRotateWithLeft(P);
            } else {
                DoubleRotateWithRight(G);
            }
        } else {  /* If S is the right child of P */
            if (G == NullNode) {
                SingleRotateWithRight(P);
            } else if (P == G->Right) {
                SingleRotateWithRight(G);
                SingleRotateWithRight(P);
            } else {
                DoubleRotateWithLeft(G);
            }
        }
    }

    return S;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
static Position SingleRotateWithLeft(Position K2) {
    Position K1;

    K1 = K2->Left;
    K1->Parent = K2->Parent;
    K2->Left = K1->Right;
    K2->Parent = K1;

    /* Connect the right child of K1 */
    if (K1->Right != NullNode) {
        K1->Right->Parent = K2;
    }

    K1->Right = K2;

    /* Determine if K1 is the left or right child of K1->Parent */
    if (K1->Parent != NullNode) {
        if (K1->Parent->Left == K2) {
            K1->Parent->Left = K1;
        } else {
            K1->Parent->Right = K2;
        }
    }

    return K1;  /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */
static Position SingleRotateWithRight(Position K1) {
    Position K2;

    K2 = K1->Right;
    K2->Parent = K1->Parent;
    K1->Right = K2->Left;
    K1->Parent = K2;

    /* Connect the left child of K2 */
    if (K2->Left != NullNode) {
        K2->Left->Parent = K1;
    }

    K2->Left = K1;

    /* Determine if K2 is the left or right child of K2->Parent */
    if (K2->Parent != NullNode) {
        if (K2->Parent->Left == K1) {
            K2->Parent->Left = K2;
        } else {
            K2->Parent->Right = K2;
        }
    }

    return K2;  /* New root */
}

/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
static Position DoubleRotateWithLeft(Position K3) {
    /* Rotate between K1 and K2 */
    K3->Left = SingleRotateWithRight(K3->Left);

    /* Rotate between K3 and K2 */
    return SingleRotateWithLeft(K3);
}

/* This function can be called only if K1 has a right */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */
static Position DoubleRotateWithRight(Position K1) {
    /* Rotate between K3 and K2 */
    K1->Right = SingleRotateWithLeft(K1->Right);

    /* Rotate between K1 and K2 */
    return SingleRotateWithRight(K1);
}

SplayTree Insert(ElementType X, SplayTree T) {
    if (T == NullNode) {
        /* Create and return a one-node tree */
        T = (SplayTree)malloc(sizeof(struct SplayNode));
        if (T == NULL) {
            FatalError("Out of space!!!");
        } else {
            T->Element = X;
            T->Parent = NullNode;
            T->Left = NullNode;
            T->Right = NullNode;
        }
    } else {
        T = Find(X, T);
        if (X != Retrieve(T)) {
            Position TmpCell;

            TmpCell = (SplayTree)malloc(sizeof(struct SplayNode));
            if (TmpCell == NULL) {
                FatalError("Out of space!!!");
            } else {
                /* Split + Join */
                TmpCell->Element = X;
                TmpCell->Parent = T->Parent;
                if (X < T->Element) {
                    /* Connect right child */
                    TmpCell->Right = T;
                    T->Parent = TmpCell;

                    /* Connect left child */
                    TmpCell->Left = T->Left;
                    if (T->Left != NullNode) {
                        T->Left->Parent = TmpCell;
                        T->Left = NullNode;
                    }
                } else {
                    /* Connect left child */
                    TmpCell->Left = T;
                    T->Parent = TmpCell;

                    /* Connect right child */
                    TmpCell->Right = T->Right;
                    if (T->Right != NullNode) {
                        T->Right->Parent = TmpCell;
                        T->Right = NullNode;
                    }
                }

                T = TmpCell;
            }
        }
    }

    return T;  /* Do not forget this line!! */
}

SplayTree Remove(ElementType X, SplayTree T) {
    if (T == NullNode) {
        Error("Element not found");
    } else {
        T = Find(X, T);
        /* Found it! */
        if (X == Retrieve(T)) {
            if (T->Left == NullNode) {
                T->Right->Parent = T->Parent;
                T = T->Right;
            } else if (T->Right == NullNode) {
                T->Left->Parent = T->Parent;
                T = T->Left;
            } else {
                Position LeftTree;

                /* Cut left subtree */
                LeftTree = T->Left;
                LeftTree->Parent = NullNode;
                T->Left = NullNode;

                /* Find max node in left subtree */
                LeftTree = FindMax(LeftTree);

                /* Connect right subtree */
                LeftTree->Right = T->Right;
                T->Right->Parent = LeftTree;

                /* Remove the found node */
                free(T);

                T = LeftTree;
            }
        }
    }

    return T;
}

Position Left(Position P) {
    return P->Left;
}

Position Right(Position P) {
    return P->Right;
}

ElementType Retrieve(Position P) {
    return P->Element;
}

// Recursive implement
// void PreorderTraversal(SplayTree T) {
//     if (T != NullNode) {
//         printf("%d ", T->Element);
//         PreorderTraversal(T->Left);
//         PreorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void PreorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NullNode || !IsEmptyStack(S)) {
            while (P != NullNode) {
                printf("%d ", P->Element);
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            P = P->Right;
        }
    }
}

// Recursive implement
// void InorderTraversal(SplayTree T) {
//     if (T != NullNode) {
//         InorderTraversal(T->Left);
//         printf("%d ", T->Element);
//         InorderTraversal(T->Right);
//     }
// }

// Non-recursive implement
void InorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position P;

        S = CreateStack();

        P = T;
        while (P != NullNode || !IsEmptyStack(S)) {
            while (P != NullNode) {
                Push(P, S);
                P = P->Left;
            }

            P = TopAndPop(S);
            printf("%d ", P->Element);
            P = P->Right;
        }
    }
}

// Recursive implement
// void PostorderTraversal(SplayTree T) {
//     if (T != NullNode) {
//         PostorderTraversal(T->Left);
//         PostorderTraversal(T->Right);
//         printf("%d ", T->Element);
//     }
// }

// Non-recursive implement
void PostorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedStack S;
        Position Pre;
        Position Cur;

        S = CreateStack();

        Cur = T;
        Pre = NullNode;
        while (Cur != NullNode || !IsEmptyStack(S)) {
            if (Cur != NullNode) {
                Push(Cur, S);
                Cur = Cur->Left;
            } else {
                Cur = Top(S);
                if (Cur->Right != NullNode && Cur->Right != Pre) {
                    Cur = Cur->Right;
                } else {
                    Pop(S);
                    printf("%d ", Cur->Element);
                    Pre = Cur;
                    Cur = NullNode;
                }
            }
        }
    }
}

void LevelorderTraversal(SplayTree T) {
    if (T != NullNode) {
        LinkedQueue Q;

        Q = CreateQueue();

        EnQueue(T, Q);

        while (!IsEmptyQueue(Q)) {
            if (Front(Q)->Left != NullNode) {
                EnQueue(Front(Q)->Left, Q);
            }

            if (Front(Q)->Right != NullNode) {
                EnQueue(Front(Q)->Right, Q);
            }

            printf("%d ", Retrieve(FrontAndDequeue(Q)));
        }
    }
}

// EOF

